package com.sparrow.common.stringmatch.trie;


import com.google.common.collect.Lists;
import com.sparrow.common.util.CollectionUtil;
import java.util.ArrayList;
import java.util.List;

/**
 * 字典树,前缀树 多叉树结构
 * 核心思想：共享公共前缀
 * 根节点不存储字符（或者存特殊标记），每条路径代表一个字符串的前缀。
 * root
 *  ├─ c
 *  │   ├─ a
 *  │   │   └─ t (isEnd=true)
 *  │   └─ o
 *  │       └─ w (isEnd=true)
 *  └─ d
 *      └─ o
 *          └─ g (isEnd=true)
 *  字典树单词 cat,cow,dog
 *  时间复杂度：O(L)，L = 字符串长度
 *
 *  常用场景
 *  1敏感词匹配，过滤
 *  2前缀统计
 *  3拼写检查/自动补全
 */
public class Trie {
    /**
     * 字典树，前缀树 节点
     */
    static class TrieNode {

        /**
         * 节点字符
         */
        public char c;

        /**
         * 该节点是否是一个敏感词的结束点
         */
        public boolean endPoint;

        /**
         * 所有子节点
         */
        public List<TrieNode> childNodes = new ArrayList<>();

        public TrieNode(char c) {
            this.c = c;
            this.endPoint = false;
        }
    }

    /**
     * 根节点
     */
    private TrieNode root = new TrieNode('R');

    /**
     * 将所有敏感词添加到根节点上
     *
     * @param words
     */
    public void load(List<String> words) {
        if (CollectionUtil.isEmpty(words)) {
            return;
        }
        root.childNodes.clear();
        for (String e : words) {
            if (e != null && e.length() > 0) {
                char[] chars = e.toLowerCase().toCharArray();
                insertNode(this.root, chars, 0);
            }
        }
    }

    /**
     * 查找子节点
     *
     * @param parentNode
     * @param c
     * @return
     */
    private TrieNode findChildNode(TrieNode parentNode, char c) {
        for (TrieNode childNode : parentNode.childNodes) {
            if (childNode.c == c) {
                return childNode;
            }
        }
        return null;
    }
    
    /**
     * 增加节点
     *
     * @param node
     * @param chars
     * @param index
     */
    private void insertNode(TrieNode node, char[] chars, int index) {
        TrieNode childNode = findChildNode(node, chars[index]);
        if (childNode == null) {
            childNode = new TrieNode(chars[index]);
            node.childNodes.add(childNode);
        }
        // 设置一个结束点
        if (index == (chars.length - 1)) {
            childNode.endPoint = true;
        }
        index++;
        if (index < chars.length) {
            insertNode(childNode, chars, index);
        }
    }

    public boolean hasNextEndPoint(TrieNode node, char[] chars, int index) {
        if (index == chars.length) {
            return false;
        }
        node = findChildNode(node, chars[index]);
        if (node == null) {
            return false;
        }
        if (node.endPoint) {
            return true;
        }
        return hasNextEndPoint(node, chars, ++index);
    }

    /**
     * 筛选替换
     * @param content
     * @param replaceWord
     * @return
     */
    public String filter(String content, char replaceWord) {
        int wordCounts = 0;
        TrieNode parentNode = root;
        char[] sources = content.toCharArray();
        char[] chars = content.toLowerCase().toCharArray();
        for (int index = 0; index < chars.length; index++) {
            if (chars[index] == ' ') {
                continue;
            }
            parentNode = findChildNode(parentNode, chars[index]);
            if (parentNode == null) {
                index = index - wordCounts;
                wordCounts = 0;
                parentNode = root;
            } else {
                wordCounts++;
                if (parentNode.endPoint && !hasNextEndPoint(parentNode, chars, index + 1)) {
                    int i = 0;
                    while (wordCounts > 0) {
                        if (sources[index - i] == ' ') {
                            i++;
                            continue;
                        }
                        sources[index - i] = replaceWord;
                        i++;
                        wordCounts--;
                    }
                    wordCounts = 0;
                    parentNode = root;
                }
                if (index == (chars.length - 1)) {
                    index = index - wordCounts + 1;
                    wordCounts = 0;
                    parentNode = root;
                }
            }
        }

        content = new String(sources);
        return content;
    }

    /**
     * 在给定内容中匹配敏感词（基于 Trie 字典树实现）。
     * @param content 待匹配的文本
     * @return 返回第一个匹配到的敏感词，如果没有匹配则返回空字符串
     */
    public String matchFirst(String content) {
        TrieNode parentNode = root;
        StringBuilder word = new StringBuilder();
        char[] chars = content.toLowerCase().toCharArray();
        for (int index = 0; index < chars.length; index++) {
            parentNode = findChildNode(parentNode, chars[index]);
            if (parentNode == null) {// 找不到此字符的子节点,也就是下一个字符开始搜索的父节点
                index = index - word.length();// 如果之前的字符有在敏感词树上匹配到,而这个敏感词匹配失败,那么从上个敏感词要重新从根节点开始找
                word.delete(0, word.length());// 清空
                parentNode = root;// 赋予根节点重新开始来过
            } else {
                word.append(chars[index]);
                if (parentNode.endPoint && !hasNextEndPoint(parentNode, chars, index + 1)) {// 如果此字符没有子节点,那么表示匹配成功,
                    return word.toString();
                }
                if (index == (chars.length - 1)) {// 最后一个字符存在敏感词节点中,但不是一个完整的敏感词,说明路径不对,从头开始找
                    index = index - word.length() + 1;
                    word.delete(0, word.length());
                    parentNode = root;
                }
            }
        }
        return word.toString();
    }

    public List<String> matchAll(String content) {
        List<String> matches = new ArrayList<>(); // 存储所有匹配到的敏感词
        TrieNode parentNode = root;
        StringBuilder word = new StringBuilder();
        char[] chars = content.toLowerCase().toCharArray();

        for (int index = 0; index < chars.length; index++) {
            parentNode = findChildNode(parentNode, chars[index]);

            if (parentNode == null) {
                // 当前字符没有对应的子节点，匹配失败，回溯
                index = index - word.length();
                word.setLength(0);
                parentNode = root;
            } else {
                // 当前字符在 Trie 中，继续匹配
                word.append(chars[index]);

                // 当前节点是敏感词末尾，并且后面没有更长匹配
                if (parentNode.endPoint && !hasNextEndPoint(parentNode, chars, index + 1)) {
                    matches.add(word.toString()); // 收集敏感词
                    // 回溯到下一个字符继续匹配
                    index = index - word.length() + 1;
                    word.setLength(0);
                    parentNode = root;
                }

                // 如果是最后一个字符，但不是完整敏感词，回溯
                if (index == chars.length - 1) {
                    index = index - word.length() + 1;
                    word.setLength(0);
                    parentNode = root;
                }
            }
        }
        return matches;
    }

    public boolean isMatch(String content) {
        return matchFirst(content).length() > 0;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.load(Lists.newArrayList("he", "she", "hers"));
        System.out.println(trie.matchAll("ushers"));
    }
}
